//***********************************希尔排序***************************************
// 3. 缩小增量多遍查找插入位置： 希尔排序
// 指定增量值Dk，每隔Dk个元素选取元素，组成了一个子序列。对子序列排序
// 重复上面的步骤，只是Dk选的会小一些
// 最后要做一次直接插入排序，Dk = 1
// 每一次的Dk必须是互质的
// 一般dk取length/2, 而后dk = dk / 2
// 希尔排序不稳定的
// 时间复杂度最好O(n)，最坏O(n²)，平均O(n^(1/3))
function shellSort(arr) {
  let n = arr.length-1;
  // 数组中每隔dk个元素组成一个数组
  for(let dk = Math.floor(n/2); dk >= 1; dk = Math.floor(dk/2)) {
    //组内直接插入排序
    for(let i = dk; i <= n; i++) {
      let temp = arr[i];
      let j = i - dk
      for(; j >= 0 && temp <= arr[j]; j = j-dk) {
        // 注意此处的步进条件为j = j - dk
        arr[j+dk] = arr[j];
      }
      arr[j+dk] = temp;
    }
  }
}
//测试用例
let arr = [96,29,54,23,83,16,32,7,10,3,5,23]
debugger;
shellSort(arr);
console.log(arr);